/**
 * @param {number[][]} tires
 * @param {number} changeTime
 * @param {number} numLaps
 * @return {number}
 */
 var minimumFinishTime = function(tires, changeTime, numLaps) {
  const n = tires.length
  let ans = 0, pre = -1
  const pq = new PriorityQueue((a,b) => {
    let [f1, r1, cnt1, t1] = a, [f2, r2, cnt2, t2] = b
    let c1 = Math.min(f1 * (r1**cnt1), f1+changeTime) 
    let c2 = Math.min(f2 * (r2**cnt2), f2+changeTime)
    if(t1 !== pre && pre !== -1) {
      c1 = Math.min(f1 * (r1**cnt1) + changeTime, f1+changeTime) 
    }
    if(t2 !== pre && pre !== -1) {
      c2 = Math.min(f2 * (r2**cnt2) + changeTime, f2+changeTime)
    }
    if(c1 === c2) {
      return f1 < f2
    }
    return c1 < c2
  })
  for(let i = 0; i<n; i++) {
    let [f, r] = tires[i]
    pq.push([f, r, 0, i])
  }
  for(let i = 0; i<numLaps; i++) {
    let [f, r, cnt, now] = pq.pop()
    if(pre !== now) {
      let x = f + changeTime
      if(i===0) x-=changeTime
      cnt = 1
      ans += x      
    } else {
      let change = f + changeTime
      if(change <= f*(r**cnt)) {
        ans += change
        cnt = 1
      } else {
        ans += f * (r**cnt)
        cnt++
      }
    }
    pre = now
    pq.push([f, r, cnt, now])
  }
  return ans
};

class PriorityQueue {
  // 默认最大堆
  constructor(
    compare = (a, b) => a > b 
    ){
    this.data = []
    this.size = 0
    this.compare = compare
  }

  peek() {
    return this.size === 0 ? null : this.data[0] 
  }

  push(val) {
    this.data.push(val)
    this._shifUp(this.size++)
  }

  pop() {
    if(this.size === 0) { return null }
    this._swap(0, --this.size)
    this._shifDown(0)
    return this.data.pop()
  }

  _parent(index) {
    return index - 1 >> 1
  }
  
  _child(index) {
    return (index << 1) + 1
  }

  _shifDown(index) {
    while(this._child(index) < this.size) {
      let child = this._child(index)
      if(child + 1 < this.size 
        && this.compare(this.data[child + 1], this.data[child])) {
          child = child + 1
      }
      if(this.compare(this.data[index], this.data[child])){
        break
      }
      this._swap(index, child)
      index = child
    }
  }

  _shifUp(index) {
    while(this._parent(index) >= 0 
    && this.compare(this.data[index], this.data[this._parent(index)])) {
      this._swap(index, this._parent(index))
      index = this._parent(index)
    }
  }

  _swap(a, b) {
    [this.data[a], this.data[b]] = [this.data[b], this.data[a]]
  }
}
